public class MergeSort extends Sort {
	
	public MergeSort(){
		super();
	}

	private <T extends Comparable<? super T>> T[] merge( T [ ] a, T [ ] tmpArray,
			int leftPos, int rightPos, int rightEnd ) {
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;
		// Main loop
		while( leftPos <= leftEnd && rightPos <= rightEnd ){
			steps++;
			if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 ){
				tmpArray[ tmpPos++ ] = a[ leftPos++ ];
			} else {
				tmpArray[ tmpPos++ ] = a[ rightPos++ ];
			}
		}
		while( leftPos <= leftEnd ) { // Copy rest of first half
			steps++;
			tmpArray[ tmpPos++ ] = a[ leftPos++ ];
		}
		while( rightPos <= rightEnd ){ // Copy rest of right half
			steps++;
			tmpArray[ tmpPos++ ] = a[ rightPos++ ];
		// Copy tmpArray back
		}
		for( int i = 0; i < numElements; i++, rightEnd-- ){
			steps++;
			a[ rightEnd ] = tmpArray[ rightEnd ];
		}
		
		return a;
	}

	/**
	 * Mergesort algorithm.
	 * @param a an array of Comparable items.
	 */
	@SuppressWarnings("unchecked")
	public <T extends Comparable<? super T>> T[] mergeSort( T [ ] a )
	{
		T [ ] tmpArray = (T []) new Comparable[ a.length ];
		return mergeSort( a, tmpArray, 0, a.length - 1 );
	}

	/**
	 * Internal method that makes recursive calls.
	 * @param a an array of Comparable items.
	 * @param tmpArray an array to place the merged result.
	 * @param left the left-most index of the subarray.
	 * @param right the right-most index of the subarray.
	 */
	
	private <T extends Comparable<? super T>> T[] mergeSort( T [ ] a, T [ ] tmpArray,
			int left, int right )
	{
		if( left < right )
		{
			steps ++;
			int center = ( left + right ) / 2;
			mergeSort( a, tmpArray, left, center );
			mergeSort( a, tmpArray, center + 1, right );
			return merge( a, tmpArray, left, center + 1, right );
		}
		return a;
	}

 }
